1. Field of the Invention
The present invention generally relates to computer graphics. More specifically, the present invention relates to a method for rendering graphical images.
2. Description of the Related Art
Computers display the image of complex models by decomposing them in to polygons. Any convex polygon can be further divided into triangles. The process of converting a triangle in to a format useful for display is called rasterization. The rasterization process samples each triangle. Samples inside a triangle are assigned values determined by the characteristics of the triangle, and samples outside of the triangle are discarded. To achieve a high quality image, the sampling must be exact. Otherwise, an error in sampling may cause visual anomalies in the final image.
The simplest method to detect the intersection of a triangle and a region is to create a bounding box around the triangle. If the bounding box touches the region of interest, then the triangle may intersect the region. Referring now to FIG. 1, where a prior art method of testing is illustrated using a bounding box 102 and a triangle 104. Three rectangular regions, A, B, and C, are tested whether they intersect with the triangle 104. First, the coordinates of the bounding box are determined by checking minimum and maximum values of x and y of the triangle 104.poly—x_low=min(x0,x1, . . . xn)poly—y_low=min(y0,y1, . . . yn)poly—x_high=max(x0,x1, . . . xn)poly—y_high=max(y0,y1, . . . yn)
Then, the coordinates of the bounding box are compared with x and y value of a rectangular region, and the results of four comparison, true or false, are ANDed.triangle_intersects_region=(poly—x_low<=region—x_high)&&(poly—y_low<=region—y_high)&&(poly—x_high>=region_x_low)&&(poly—y_high>=region—y_low)
The intersection test is conservative and simple. However, a thin triangle with diagonal orientation may generate many false positives. The number of false positives is inversely proportional to the ratio of the triangle area to the bounding box area. Further, while the bounding box test alone is efficient, it is not very accurate. For rectangular regions A 106, B 108, and C 110, triangle_intersects_region would be TRUE for rectangular regions A 106, B 108, and C 110. However, for regions B 108 and C 110, the results would be false positives, and only region A 106 intersects the triangle 104.
To exactly determine if a triangle intersects a region, the appropriate corner of the region needs to be checked against each edge of the triangle. If every edge of the triangle has at least one corner of the region on the same side as the interior of the triangle, then the triangle and the region intersect. For example, in FIG. 2, corner 202 of region A 106 is in the same side as the interior 210 of the original triangle 104 for all three edges 204, 206, and 208 of the triangle 104. On the other hand, region B 108 does not have any corner that is in the same side as the interior 208 for all three edges 204, 206, and 208 of the triangle 104. Therefore, region B 108 does not intersect with the triangle 104.
To determine the intersection, a cross product must be computed for each edge. The sign of the cross product determines if that edge contains a corner of the region.cp—n=(corner—x—n−x—0—n)*(y—1—n−y—0—n)−(corner—y—n−y—0—n)*(x—1—n−x—0—n)
where:                (corner_x_n, corner_y_n) is a corner of the region n.        (x—0_n, y—0_n) is one vertex of the nth edge        (x—1_n, y—1_n) is the other vertex of the nth edge        
The precision of the math needed to compute the cross product is determined by the precision of the vertices and the granularity of the grid that determines the regions. A finer sampling grid, or higher vertex precision, will require more circuitry to compute the cross product. High vertex precision may require a large amount of circuitry. Consequently, the exact intersection test is accurate, but inefficient.
In the example of the prior art method used in FIG. 2, the top-left corner of region A 106 and region B 108 are on the interior side of the right edges 204 and 206 of the triangle 104. The bottom-right corner of region A 106 is on the interior side of the left edge 208 of the triangle 104, but the bottom-right corner of region B 108 is not. Therefore, the triangle 104 intersects region A 106, but not region B 108.
The cp_n calculation is intensive because it involves subtraction of two x coordinates and two y coordinates and multiplication of the results of these subtractions, where each coordinate is represented by an integer and a fraction. For example, for a system where each coordinate employs 15 bits to represent the integer part and 10 bits to represent the fraction part, the calculation of cp_n involves 25 bit subtractors and 25 bit multipliers, and the result would be a 50 bit number.